Packrat Parsers Can Support Left Recursion (2008)
Packrat parsing offers several advantages over other parsing techniques, such as the guarantee of linear parse times while supporting backtracking and unlimited look-ahead.
packrat parsingは他のパース技法に対して、いくつかの利点がある
線形のパース時間の保証
バックトラッキングや制限ない先読みのサポート
Unfortunately, the limited support for left recursion in packrat parser implementations makes them difficult to use for a large class of grammars (Java’s, for example).
残念ながら、packrat parserの実装は左再帰を制限付きでしかサポートしないため、文法の大きなクラスにおける利用は困難となっている
This paper presents a modification to the memoization mechanism used by packrat parser implementations that makes it possible for them to support (even indirectly or mutually) left-recursive rules.
この論文は、packrat parserの実装によって使われるメモ機構において、左再帰のルールを(間接的、双方的であっても)サポートできるようにする修正を示す
While it is possible for a packrat parser with our modification to yield super-linear parse times for some left-recursive grammars, our experiments show that this is not the case for typical uses of left recursion.
我々の提案する修正をしたpackrat parserはいくつかの左再帰の文法について線形を超えるパース時間を引き起こしたが、実験によりこれは左再帰の典型的な使用ではないことを示す
参考文献